package dynamicProgramming.knapsack;

/**
 * @author zxc
 * @date 2023/01/26 09:59
 **/

/**
 * 题目 ：加减目标值
 * 题目详述 ：
 * 给定一个正整数数组 nums 和一个整数 target 。
 * 向数组中的每个整数前添加'+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 *
 * 提示：
 * 1 <= nums.length <= 20
 * 0 <= nums[i] <= 1000
 * 0 <= sum(nums[i]) <= 1000
 * -1000 <= target <= 1000
 */
public class FindTargetSumWays {
    /**
     * 思路 ：
     * 即，问题转换 :
     * 假设 ：p为所需要累加的数字集合;q为所需要累减的数字集合;sum为所有数组元素和;target为所要求的目标值
     * p + q = sum  && p - q = target
     * ===> 2*p = (sum + target)
     * ===> 即，转换为 在nums数组中寻找累加值等于(sum + target) / 2的数组元素集合;
     *
     * 状态转移方程 ：
     * 假设f(i,j)为在前i个数组元素中选择若干个元素填满容量为j的背包的数目;
     * （1）当j == 0（即，背包容量j为0），必然为1（即，nums数组中每个元素都不去进行选择）
     * （2）当i == 0 && j > 0（即，物品数量为0/数组nums == 0）,必然为0（即，不成立）
     * （3）当i > 0 && j > nums[i]时，===》 f(i,j) = f(i-1,j) + f(i-1,j-nums[i]);
     *
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 特殊情况1 ：若是数组中元素值之和sum < 目标元素值target的话，即不成立;
        // 特殊情况2 ：若是(sum + target) % 2 == 1,也是不成立的;
        // ===> 即，sum + target为奇数的话，同时又由于背包容量j == (sum + target) / 2;
        if(sum < target || (sum + target) % 2 == 1){
            return 0;
        }
        return findTarget(nums , (sum + target) / 2);
    }

    private int findTarget(int[] nums, int target) {
        // 即，使用二维数组temp[2][nums.length]来保存计算过程中结果;
        int[][] temp = new int[2][target + 1];
        // 极端特殊情况 ：即，物品数量 == 0 && 背包容量 == 0
        // ===》 即，不取任何物品为 一种情况;
        temp[0][0] = 1;
        // 遍历nums数组中的所有元素;
        // 特殊情况 ：若是target为负数时，则不会进入内层for循环，即直接返回数组中的初始值0;
        for(int i = 1; i <= nums.length ; i++){
            // 由于取值范围 0 <= nums[i] <= 1000，即nums[i]是可以取值取到0的;
            // 所以temp[i][0]并不一定等于1;
            // ===》 若是temp数组中存在多个0元素的话，则temp[i][0] = 2的n-1次方;
            for(int j = 0; j <= target; j++){
                // 即，temp[i][j]由temp[i-1][j]（即，第i个元素并不加入背包中）
                // && temp[i-1][j - nums[i]]（即，第i个元素加入到背包，背包容量发生变化）
                if(j >= nums[i - 1]){
                    //（1）背包容量足够大，能够将第i个元素加入到背包中;
                    temp[i % 2][j] = temp[(i - 1) % 2][j] + temp[(i - 1) % 2][j - nums[i - 1]];
                }
                else {
                    //（2）背包容量不大，同时不能够将第i个元素加入到背包中;
                    temp[i % 2][j] = temp[(i - 1) % 2][j];
                }
            }
        }
        // 返回从nums数组中拿取元素 && 背包容量为target 所有可能情况;
        return temp[nums.length % 2][target];
    }
}
